NP-completo

NP-completo
En teoría de la complejidad computacional, la clase de complejidad NP-completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completo. Se puede decir que los problemas de NP-completo son los problemas más difíciles de NP y muy probablemente no formen parte de la clase de complejidad P. La razón es que de tenerse una solución polinómica para un problema de NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico.

Enciclopedia Universal. 2012.

Игры ⚽ Поможем написать курсовую

Mira otros diccionarios:

  • completo — completo, ta adjetivo 1. (estar) Que tiene todas las partes que lo componen: La colección está completa. 2. (antepuesto / pospuesto) Que es total en todos sus aspectos: La fiesta ha sido un completo fracaso. La victoria ha sido completa. Sinónimo …   Diccionario Salamanca de la Lengua Española

  • completo — completo, ta adjetivo 1 entero*, íntegro, cabal, acabado, perfecto, lleno, cumplido, exacto. Íntegro equivale a entero; cabal reúne los matices de completo y entero. Cuando se trata de un trabajo u obra terminados, decimos que están completos,… …   Diccionario de sinónimos y antónimos

  • completo — completo, ta (Del lat. complētus, part. pas. de complēre, terminar, completar). 1. adj. Lleno, cabal. 2. Acabado, perfecto. por completo. loc. adv. completamente. ☛ V. dentición completo, flor completo, pensión completo …   Diccionario de la lengua española

  • completo — /kom plɛto/ [dal lat. completus, part. pass. di complēre compiere ; come s.m., nel sign. 2, dal fr. complet ]. ■ agg. 1. a. [che ha tutte le sue parti] ▶◀ compiuto, definitivo, finito, intero, perfetto, sano. ◀▶ imperfetto, incompiuto, incompleto …   Enciclopedia Italiana

  • Completo — puede referirse a: Algo íntegro, lleno, pleno, cumplido, acabado, perfecto. Espacio completo, en matemáticas. Completo, sándwich típico chileno, similar al hot dog. Véase también Completas, la última oración de la liturgia de las Horas… …   Wikipedia Español

  • completo — |é| adj. 1. A que não falta nada. 2. Que tem todas as qualidades exigidas. 3. Perfeito. 4. Que não admite mais, cheio. 5. Cabal; satisfeito. 6. Total; pleno. • s. m. 7. Estado do que se acha completo …   Dicionário da Língua Portuguesa

  • completo — (Del lat. completus, lleno.) ► adjetivo 1 Que tiene todos los elementos o partes que normalmente lo componen: ■ me han regalado una cubertería completa. SINÓNIMO entero íntegro ANTÓNIMO incompleto 2 Que está lleno: ■ la sala está completa …   Enciclopedia Universal

  • Completo (gastronomía) — Un completo italiano siendo degustado. El completo es un sándwich que corresponde a una variación chilena del perrito caliente. Consiste en un pan alargado con una salchicha en el medio, acompañada de distintos ingredientes. Es el sándwich más… …   Wikipedia Español

  • completo — com·plè·to agg., s.m. FO I. agg. I 1. di qcs., che ha tutti gli elementi che deve o può avere: un elenco, un resoconto completo; aspirapolvere completo di accessori; opera completa di un autore, edizione che comprende tutti i suoi scritti; avere… …   Dizionario italiano

  • Completo — Chilean Completo A completo italiano Origin Place of origin Chile Dish details …   Wikipedia

  • completo — adj 1 Que tiene todas sus partes o elementos, que contiene todo lo que debe contener: un aparato completo, cupo completo 2 Que está terminado o que ha alcanzado su carácter definitivo: una obra completa, un éxito completo, un completo acuerdo,… …   Español en México

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”